﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.

We shall define the triplet of positive integers (a, b, c) to be an abc-hit if:

    GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
    a < b
    a + b = c
    rad(abc) < c

For example, (5, 27, 32) is an abc-hit, because:

    GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
    5 < 27
    5 + 27 = 32
    rad(4320) = 30 < 32

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with ∑c = 12523.

Find ∑c for c < 120000.

Note: This problem has been changed recently, please check that you are using the right parameters.

     * */
    class Problem127 : IProblem
    {
        //vrlo spora verzija -.- cca 40 min

        SieveOfAtkin sieve;
        public string Calculate()
        {
            int limit = 120000;

            p = new int[limit];
            p[0] = 2;
            sieve = new SieveOfAtkin(limit * 10);
            for (int i = 1, j = 3; i < p.Length; i++)
            {
                while (!sieve.IsPrime(j))
                    j += 2;
                p[i] = j;
                j += 2;
            }


            int c = 1;

            memo[1] = 1;

            long sum = 0;
            int count = 0;

            while (c < limit)
            {
                c++;
                radProduct(c);

                int a = 0;
                while (true)
                {
                    a++;

                    int b = c - a;

                    if (a >= b)
                        break;

                    if (CommonFunctions.GreatestCommonDivisor(memo[a], memo[c]) == 1)
                    {
                        long rad = memo[a] * (long)memo[b] * (long)memo[c];

                        if (rad < c)
                        {
                            Console.WriteLine("{0}, {1}, {2}", a, b, c);
                            count++;
                            sum += c;
                        }
                    }
                }

            }

            Console.WriteLine("count = {0}", count);

            return sum.ToString();
        }

        int[] memo = new int[120001];

        int[] p;
        public int radProduct(int n)
        {
            if (n == 1)
                return 1;

            if (memo[n]!=0)
                return memo[n];

            if (sieve.IsPrime(n))
            {
                memo[n] = n;
                return n;
            }

            int product = 1;
            int i = 0;
            int tempN = n;

            
            while (n > 1 && i < p.Length)
            {

                if (p[i] > Math.Sqrt(n))
                {
                    product *= n;
                    n = 1;
                    break;
                }


                if (n % p[i] == 0)
                {
                    product *= p[i];

                    while (n % p[i] == 0)
                        n /= p[i];
                }
                i++;
            }



            if (n != 1)
            {


                int prime = p[p.Length - 1];
                while (n > 1)
                {
                    prime += 2;
                    if (sieve.IsPrime(prime))
                    {
                        if (n % prime == 0)
                        {
                            product *= prime;

                            while (n % prime == 0)
                                n /= prime;
                        }
                    }
                }
            }

            memo[tempN] = product;
            return product;
        }
    }
}
